package com.atguigui.leetcode1;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 1079.活字印刷
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/5/19 8:54
 */
public class P1079LetterTilePossibilities {
    public static void main(String[] args) {
        Solution solution = new P1079LetterTilePossibilities().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int numTilePossibilities(String tiles) {
            Map<Character, Integer> count = new HashMap<>();
            for (char t : tiles.toCharArray()) {
                count.put(t, count.getOrDefault(t, 0) + 1);
            }
            Set<Character> tile = new HashSet<>(count.keySet());
            return dfs(tiles.length(), count, tile) - 1;
        }

        private int dfs(int i, Map<Character, Integer> count, Set<Character> tile) {
            if (i == 0) {
                return 1;
            }
            int res = 1;
            for (char t : tile) {
                if (count.get(t) > 0) {
                    count.put(t, count.get(t) - 1);
                    res += dfs(i - 1, count, tile);
                    count.put(t, count.get(t) + 1);
                }
            }

            return res;
        }
    }
}
